package cn.demoncat.util.lang.entity.data;

import java.util.function.Consumer;

/**
 * 二叉排序树（BST, Binary Sort Tree）
 * 
 * 性质：有序排列结点
 * 
 * @author 延晓磊
 *
 * @since 2020年7月22日
 */
public class SortBinaryTree<T extends Comparable<T>> extends BinaryTree<T> {
	
	/**
	 * 添加
	 * 
	 * @param data	数据
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public SortBinaryTree<T> add(T data) {
		return add(new BinaryTreeNode<>(data));
	}
	
	/**
	 * 添加
	 * 
	 * @param node	结点（将清除子结点）
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public SortBinaryTree<T> add(BinaryTreeNode<T> node) {
		// 清除子结点
		node.left = null;
		node.right = null;
		// 添加
		if (root == null) {
			root = node;
		}else {
			add(root, node);
		}
		return this;
	}
	
	/**
	 * 查找结点
	 * 
	 * @param data	数据
	 * 
	 * @return	第一个查找到（compare）的结点（含parent），未找到返回null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	@Override
	public BinaryTreeNode<T> search(T data){
		if (root == null) {
			return null;
		}
		return search(root, data);
	}
	
	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-删除子树
	 * 
	 * @param data	目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	@Override
	public boolean removes(T data) {
		if (root != null) {
			// 判断根结点
			if (data.compareTo(root.data) == 0) {
				// 删除根结点
				root = null;
				return true;
			}else {
				// 查找结点
				BinaryTreeNode<T> node = search(data);
				if (node != null) {
					if (node.parent.left == node) {
						node.parent.left = null;
					}else {
						node.parent.right = null;
					}
					return true;
				}
			}
		}
		return false;
	}
	
	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-提升子结点
	 * 
	 * @param data	目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年7月23日
	 */
	public boolean remove(T data) {
		return remove(data, null);
	}
	
	
	/**
	 * 查找结点：compare == equals
	 * 
	 * @param node	当前结点
	 * @param data	目标数据
	 * 
	 * @return 匹配的结点（含parent）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	private BinaryTreeNode<T> search(BinaryTreeNode<T> node, T data) {
		// 比较
		int cp = data.compareTo(node.data);
		if (cp == 0) {
			// data == node = 匹配结点
			return node;
		}else if (cp < 0) {
			// data < node = 查找左子树
			if (node.left == null) {
				return null;
			}
			node.left.parent = node;
			return search(node.left, data);
		}else {
			// data > node = 查找右子树
			if (node.right == null) {
				return null;
			}
			node.right.parent = node;
			return search(node.right, data);
		}
	}
	
	/**
	 * 添加结点
	 * 
	 * @param parent		父结点
	 * @param node			结点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	protected void add(BinaryTreeNode<T> parent, BinaryTreeNode<T> node) {
		if (node.data.compareTo(parent.data) < 0) {
			// node < parent = 左子树
			if (parent.left == null) {
				parent.left = node;
			}else {
				add(parent.left, node);
			}
		}else {
			// node >= parent = 右子树
			if (parent.right == null) {
				parent.right = node;
			}else {
				add(parent.right, node);
			}
		}
	}
	
	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-提升子结点
	 * 
	 * @param data	目标数据（删除第一个匹配到的结点）
	 * @param fn	消费（父结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年7月23日
	 */
	protected boolean remove(T data, Consumer<BinaryTreeNode<T>> fn) {
		// 判断是否为空树
		if (root == null) {
			return false;
		}
		// 查找待删除的结点
		BinaryTreeNode<T> node = search(data);
		if (node == null) {
			return false;
		}
		// 删除结点
		if (node.left == null && node.right == null) {
			// 1、叶子结点：置空结点
			if (node == root) {
				// 根结点
				root = null;
			}else {
				// 子结点
				if (node.parent.left == node) {
					node.parent.left = null;
				}else {
					node.parent.right = null;
				}
				// 处理父结点
				if (fn != null) {
					fn.accept(node.parent);
				}
			}
		}else if(node.left != null && node.right != null) {
			// 2、满分枝结点：替换右侧最小结点/左侧最大结点
			BinaryTreeNode<T> rightMinParent = node;
			BinaryTreeNode<T> rightMin = node.right;
			while (rightMin.left != null) {
				// 找到右侧最小结点
				rightMinParent = rightMin;
				rightMin = rightMin.left;
			}
			// 删除右侧最小结点（叶子结点）
			if (rightMinParent == node) {
				rightMinParent.right = null;
			}else {
				rightMinParent.left = null;
			}
			// 替换结点的值
			node.setData(rightMin.data);
			// 处理父结点
			if (fn != null) {
				// 删除满分枝结点，实际是删除结点的右侧最小结点，然后替换其值
				fn.accept(rightMinParent);
			}
		}else {
			// 3、半分枝结点：提升子结点
			if (node.left != null) {
				// 提升左结点
				if (node == root) {
					// 根结点
					root = node.left;
				}else {
					// 子结点
					if (node.parent.left == node) {
						node.parent.left = node.left;
					}else {
						node.parent.right = node.left;
					}
					// 处理父结点
					if (fn != null) {
						fn.accept(node.parent);
					}
				}
			}else {
				// 提升右结点
				if (node == root) {
					// 根结点
					root = node.right;
				}else {
					// 子结点
					if (node.parent.left == node) {
						node.parent.left = node.right;
					}else {
						node.parent.right = node.right;
					}
					// 处理父结点
					if (fn != null) {
						fn.accept(node.parent);
					}
				}
			}
		}
		return true;
	}

}
